# -*- coding: utf-8 -*-            
# @Time : 2022/11/24 22:23
# @Author  : lining
# @FileName: 冒泡排序.py
"""
冒泡排序：最小的在最右边
最好O(n),最坏O(n*n)，是原地排序（空间复杂度为O(1)）,排序后原来顺序的元素之间为位置还是没有变化，是稳定的排序算法
有序度 （1，2）（2，3）（1，3）这种是有序的
1，2，4，3 ，3 排序后1，2，3，3，4  两个3之间的顺序相对之前没有变化
"""
import time


class BubbleSort():
    def bubblesort(self, data):
        # 优化：如果这一轮没有交换过数据就代表剩下的数据已经有序，就直接退出
        change = True
        len_data = len(data)
        start_time = time.perf_counter()
        for i in range(len_data):
            for y in range(i+1, len_data):
                if data[i]<data[y]:
                    data[y], data[i] = data[i], data[y]
                    change = False
            if change:
                break
        print(data)
        print(time.perf_counter()-start_time)


a = [6,5,4,1,5,2,3,4,6,3,8,9]
b = [5,4,3,2,1]
BubbleSort().bubblesort(a)

